Carmichael Function

In number theory, a branch of mathematics, the Carmichael function of a positive integer is the smallest positive integer such that
:$a^m \equiv 1 \pmod$
holds for every integer coprime to . In algebraic terms, is the exponent of the multiplicative group of integers modulo .

The Carmichael function is named after the American mathematician Robert Carmichael who defined it in 1910. It is also known as Carmichael's λ function, the reduced totient function, and the least universal exponent function.

The following table compares the first 36 values of with Euler's totient function (in bold if they are different; the s such that they are different are listed in ).

Numerical examples

# Carmichael's function at 5 is 4, , because for any number 0 coprime to 5, i.e. $a\in \~,$ there is $a^m \equiv 1 \,(\text 5)$ with $m=4,$ namely, , , and . And this is the smallest exponent with this property, because $2^2 =4 \not\equiv 1 \,(\text 5)$ (and $3^2 = 9 \not\equiv 1 \,(\text 5)$ as well.)
Moreover, Euler's totient function at 5 is 4, , because there are exactly 4 numbers less than and coprime to 5 (1, 2, 3, and 4). Euler's theorem assures that for all coprime to 5, and 4 is the smallest such exponent.
# Carmichael's function at 8 is 2, , because for any number coprime to 8, i.e. $a\in \~,$ it holds that . Namely, , , and .
Euler's totient function at 8 is 4, , because there are exactly 4 numbers less than and coprime to 8 (1, 3, 5, and 7). Moreover, Euler's theorem assures that for all coprime to 8, but 4 is not the smallest such exponent.

Computing with Carmichael's theorem

By the unique factorization theorem, any can be written in a unique way as
:$n= p_1^p_2^ \cdots p_^$
where are primes and are positive integers. Then is the least common multiple of the of each of its prime power factors:
:$\lambda(n) = \operatorname\Bigl(\lambda\left(p_1^\right),\lambda\left(p_2^\right),\ldots,\lambda\left(p_k^\right)\Bigr).$
This can be proved using the Chinese remainder theorem.

Carmichael's theorem explains how to compute of a prime power : for a power of an odd prime and for 2 and 4, is equal to the Euler totient ; for powers of 2 greater than 4 it is equal to half of the Euler totient:

:$\lambda(p^r) = \begin \tfrac12\varphi\left(p^r\right)&\textp=2\land r\geq 3 \;(\mboxp^r = 8,16,32,64,128,256,\dots)\\ \varphi\left(p^r\right) &\mbox\;(\mboxp^r = 2,4,3^r,5^r,7^r,11^r,13^r,17^r,19^r,23^r,29^r,31^r,\dots) \end$

Euler's function for prime powers is given by
:$\varphi(p^r) = p^(p-1).$

Properties of the Carmichael function

In this section, an integer $n$ is divisible by a nonzero integer $m$ if there exists an integer $k$ such that $n = km$. This is written as
:$m \mid n.$

Order of elements modulo '

Let and be coprime and let be the smallest exponent with , then it holds that
:$m \,, \, \lambda(n)$.
That is, the order of a unit in the ring of integers modulo divides and
:$\lambda(n) = \max\$

Minimality

Suppose for all numbers coprime with . Then .

Proof: If with , then
:$a^r = 1^k \cdot a^r \equiv \left(a^\right)^k\cdot a^r = a^ = a^m \equiv 1\pmod$
for all numbers coprime with . It follows , since and the minimal positive such number.

divides

This follows from elementary group theory, because the exponent of any finite group must divide the order of the group. is the exponent of the multiplicative group of integers modulo while is the order of that group. In particular, the two must be equal in the cases where the multiplicative group is cyclic due to the existence of a primitive root, which is the case for odd prime powers.

We can thus view Carmichael's theorem as a sharpening of Euler's theorem.

Divisibility

:$a\,, \,b \Rightarrow \lambda(a)\,, \,\lambda(b)$

Proof.

By definition, for any integer $k$, we have that $b \,, \, (k^ - 1)$ , and therefore $a \,, \, (k^ - 1)$. By the minimality property above, we have $\lambda(a)\,, \,\lambda(b)$.

Composition

For all positive integers and it holds that
:$\lambda(\mathrm(a,b)) = \mathrm(\lambda(a), \lambda(b))$.
This is an immediate consequence of the recursive definition of the Carmichael function.

Exponential cycle length

If $r_=\max_i\$ is the biggest exponent in the prime factorization $n= p_1^p_2^ \cdots p_^$ of , then for all (including those not coprime to ) and all ,

:$a^r \equiv a^ \pmod n.$

In particular, for square-free (), for all we have

:$a \equiv a^ \pmod n.$

Extension for powers of two

For coprime to (powers of) 2 we have for some . Then,

:$a^2 = 1+4h(h+1) = 1+8C$

where we take advantage of the fact that is an integer.

So, for , an integer:

:$\begin a^&=1+2^k h \\ a^&=\left(1+2^k h\right)^2=1+2^\left(h+2^h^2\right) \end$

By induction, when , we have
:$a^\equiv 1\pmod.$

It provides that is at most .

Average value

For any :Sándor & Crstici (2004) p.194

:$\frac \sum_ \lambda (i) = \frac e^$

(called Erdős approximation in the following) with the constant

:$B := e^ \prod_ \left(\right) \approx 0.34537$
and , the Euler–Mascheroni constant.

The following table gives some overview over the first values of the function, for both, the exact average and its Erdős-approximation.

Additionally given is some overview over the more easily accessible with
* .
There, the table entry in row number 26 at column
* → 60.49
indicates that 60.49% (≈ ) of the integers have meaning that the majority of the values is exponential in the length of the input , namely
:$\left(2^\frac45\right)^l = 2^\frac = \left(2^l\right)^\frac45 = n^\frac45.$

:

Prevailing interval

For all numbers and all but positive integers (a "prevailing" majority):
:$\lambda(n) = \frac$
with the constant

:$A := -1 + \sum_ \frac \approx 0.2269688$

Lower bounds

For any sufficiently large number and for any , there are at most
:$N\exp\left(-0.69(\Delta\ln\Delta)^\frac13\right)$
positive integers such that .

Minimal order

For any sequence of positive integers, any constant , and any sufficiently large :Theorem 1 in Erdős 1991Sándor & Crstici (2004) p.193
:$\lambda(n_i) > \left(\ln n_i\right)^.$

Small values

For a constant and any sufficiently large positive , there exists an integer such that
:$\lambda(n)<\left(\ln A\right)^.$
Moreover, is of the form
:$n=\mathop_q$
for some square-free integer .

Image of the function

The set of values of the Carmichael function has counting function
:$\frac ,$
where
:$\eta=1-\frac \approx 0.08607$

Use in cryptography

The Carmichael function is important in cryptography due to its use in the RSA encryption algorithm.

See also

* Carmichael number

Notes

References

*
*
*
*

{{Totient

Modular arithmetic
Functions and mappings